package com.yoshino.leetcode.oneHundred.twentyth;

import java.util.HashMap;
import java.util.Map;

class Solution {
    // 先序遍历：根结点 | 左结点 | 右节点
    // 中序遍历：左结点 | 根结点 | 右节点
    private int[] preorder;
    private Map<Integer, Integer> maps = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < preorder.length; i++) {
            maps.put(inorder[i], i);
        }
        return recur(0, 0, preorder.length - 1);
    }

    private TreeNode recur(int root, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int ind = maps.get(preorder[root]);
        node.left = recur(root + 1, left, ind - 1);
        node.right = recur(root + ind - left + 1, ind + 1, right);
        return node;
    }

    public double myPow(double x, int n) {
        boolean flag = n < 0;
        if (n == 0 || x == 1) {
            return 1;
        } else {
            return flag ? 1 / zsPow(x, -(long) n) : zsPow(x, n);
        }
    }

    private double zsPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        double half = zsPow(x, n / 2);
        double mod = zsPow(x, n % 2);
        return half * half * mod;
    }

    private int[] postorder;
    public boolean verifyPostorder(int[] postorder) {
        this.postorder = postorder;
        return verifyPostorder(0, postorder.length - 1);
    }

    private boolean verifyPostorder(int left, int right) {
        if (left < right) {
            int mid = postorder[right], ind = 0;
            boolean flag = true;
            for (int i = right - 1; i >= left; i--) {
                if (postorder[i] > mid) {
                    if (!flag) {
                        return false;
                    }
                } else {
                    if (flag) {
                        ind = i;
                    }
                    flag = false;
                }
            }
            return verifyPostorder(left, ind) && verifyPostorder(ind + 1, right - 1);
        }
        return true;
    }

}